一、计算机的算法具有哪些特性

计算机的算法具有可行性，有穷性、输入\输出、确定性。

计算机算法特征

1.有穷性。壹个算法应包含有限的操作流程，而不能是无限的。事实上“有穷性”往往指“在合理的范围之内”。如果让计算机执行壹个历时1000年才结束的算法，这虽然是有穷的，但超过了合理的限度，大众不把他视为有效算法。

2.确定性。算法中的每壹个流程都应当是确定的，而不应当是含糊的、模棱两可的。算法中的每壹个流程应当不致被解释成不同的含义，而应是特别明确的。也就是说，算法的含义应当是唯一的，而不应当产生“歧义性”。

3.有零个或多个输入、所谓输入是指在执行算法是需要从外界取得必要的信息。

4.有壹个或多个输出。算法的目的是为了求解，没有输出的算法是没有意义的。

5.有效性。算法中的每壹个流程都应当能有效的执行。并得到确定的结局。

拓展资料：

重要算法

A*搜寻算法

俗称A星算法。这是一种在图形平面上，有多个节点的途径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短途径；也像BFS一样，进行启发式的搜索。

Beam Search

束搜索(beam search)方式是化解优化难题的一种启发式方式，它是在分枝定界方式基础上进步起来的，它运用启发式方式估计k个最好的途径，仅从这k个途径出发给下搜索，即每一层只有满意的结点会被保留，其它的结点则被永久抛弃，从而比分枝定界法能大大节省运行时刻。束搜索于20世纪70年代中期首先被应用于人工智能领域,1976年Lowerre在其称为HARPY的语音识别体系中第一次运用了束搜索方式。他的目标是并行地搜索多少潜在的最优决策途径以减少回溯，并快速地获取壹个解。

二分取中查找算法

一种在有序数组中查找某一特定元素的搜索算法。搜索经过从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索经过结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始相对。这种搜索算法每一次相对都使搜索范围缩小一半。

Branch and bound

分支定界(branch and bound)算法是一种在难题的解空间树上搜索难题的解的方式。但和回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方式搜索解空间树，在分支定界算法中，每壹个活结点只有一次机会成为扩展结点。

数据压缩

数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术。数据压缩在文件存储和分布式体系领域有着特别广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。

Diffie–Hellman密钥协商

Diffie–Hellman key exchange，简称“D–H”，是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起壹个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。

Dijkstra’s算法

迪科斯彻算法（Dijkstra）是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）发明的。算法化解的是有给图中单个源点到其他顶点的最短途径难题。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间发车行经的距离，迪科斯彻算法可以用来找到两个城市之间的最短途径。

动态规划

动态规划是一种在数学和计算机科学中运用的，用于求解包含重叠子难题的最优化难题的方式。其基本想法是，将原难题分解为相似的子难题，在求解的经过中通过子难题的解求出原难题的解。动态规划的想法是多种算法的基础，被广泛应用于计算机科学和工程领域。相对著名的应用实例有：求解最短途径难题，背包难题，项目管理，网络流优化等。这里也有一篇文章说得相对详细。

欧几里得算法

在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法第一次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

最大期望（EM）算法

在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器进修和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个流程交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在 E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下壹个 E步计算中，这个经过不断交替进行。

快速傅里叶变换(FFT)

快速傅里叶变换（Fast Fourier Transform，FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。

哈希函数

HashFunction是一种从任何一种数据中创建小的数字“指纹”的方式。该函数将数据打乱混合，从头创建壹个叫做散列值的指纹。散列值通常用来代表壹个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来不同差异数据，会使得数据库记录更难找到。

堆排序

Heapsort是指利用堆积树（堆）这种数据结构所设计的一种排序算法。堆积树一个近似完全二叉树的结构，并同时满足堆积属性：即子结点的键值或索引总是小于（或者大于）它的父结点。

归并排序

Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的壹个特别典型的应用。

RANSAC算法

RANSAC是”RANdom SAmpleConsensus”的缩写。该算法是用于从一组观测数据中估计数学模型参数的迭代方式，由Fischler and Bolles在1981提出，它是一种非确定性算法，由于它只能以一定的概率得到合理的结局，随着迭代次数的增加，这种概率是增加的。该算法的基本假设是观测数据集中存在”inliers”（那些对模型参数估计起到支持影响的点）和”outliers”（不符合模型的点），而且这组观测数据受到噪声影响。RANSAC假设给定一组”inliers”数据就能够得到最优的符合这组点的模型。

RSA加密演算法

这一个公钥加密算法，也是全球上第壹个适合用来做签名的算法。今天的RSA已经专利失效，其被广泛地用于电子商务加密，大家都相信，只要密钥足够长，这个算法就会是安全的。

并查集Union-find

并查集是一种树型的数据结构，用于处理一些不相交集中（Disjoint Sets）的合并及查询难题。常常在运用中以森林来表示。

Viterbi algorithm

寻找最也许的隐藏情形序列(Finding most probable sequence of hidden states)。

参考资料：计算机算法

二、计算机算法必须具备5个特性

计算机算法是对计算机上执行的计算经过的具体描述，或者说是以一步一步的方法来描述计算机怎样将输入转化为所标准的输出的经过。计算机算法具有下面内容五个特性：

1、有穷性：壹个计算机算法应包含有限的操作流程，而不能是无限的。事实上“有穷性”往往指“在合理的范围之内”，超过了合理的限度，大众把他视为无效算法。

2、确定性：计算机算法中的每壹个流程都应当是确定的，而不应当是含糊的、模棱两可的。也就是说，计算机算法的含义应当是唯一的，而不能当产生“歧义性”。

3.、有零个或多个输入：计算机算法输入是指在执行算法是需要从外界取得必要的信息。

4、有壹个或多个输出：计算机算法的目的是为了求解，没有输出的算法是没有任何意义的。

5、有效性：计算机算法中的每壹个流程都应保证能有效的执行，并得到确定的结局。

扩展资料

壹个计算机算法除了具备上述5个特性，还应具备下面内容4个条件：

1、计算机算法首先必须是正确的，即对于任意的一组输入，包括合理的输入和不合理的输入，总能得到预期的输出。

2、计算机算法必须是由一系列具体流程组成的，而且每一步都能够被计算机所领会和执行，而不是抽象和模糊的概念。

3、计算机算法的每壹个流程都有确定的执行顺序，即上一步在哪里里，下一步是啥子，都必须明确。

4、无论壹个计算机算法有多复杂，都必须在有限流程之后终止运行，即流程必须是有限的。在任何情况下，都不能陷入无限循环中。

三、高分求动态规划题目!!!

这是大家计算机系算法设计课的实验课程，下面是动态规划内容：

实验四：动态规划

实验目的：领会动态规划的基本想法，领会动态规划算法的两个基本要素最优子结构性质和子难题的重叠性质。熟练掌握典型的动态规划难题。掌握动态规划想法解析难题的一般方式，对较简单的难题能正确解析，设计出动态规划算法，并能快速编程实现。

实验内容：编程实现讲过的例题：最长公共子序列难题、矩阵连乘难题、凸多边形最优三角剖分难题、电路布线难题等。本实验中的难题，设计出算法并编程实现。

习题

1．最长公共子序列

壹个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1, x2,…, xm>，则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在壹个严格递增的下标序列<i1, i2,…, ik>，使得对于全部j=1,2,…,k有

解答如下：

a)最长公共子序列的结构

若用穷举搜索法，耗时太长，算法需要指数时刻。

易证最长公共子序列难题也有最优子结构性质

设序列X=<x1, x2,…, xm>和Y=<y1, y2,…, yn>的壹个最长公共子序列Z=<z1, z2,…, zk>，则：

i.若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；

ii.若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；

iii.若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=<x1, x2,…, xm-1>，Yn-1=<y1, y2,…, yn-1>，Zk-1=<z1, z2,…, zk-1>。

最长公共子序列难题具有最优子结构性质。

b)子难题的递归结构

由最长公共子序列难题的最优子结构性质可知，要找出X=<x1, x2,…, xm>和Y=<y1, y2,…, yn>的最长公共子序列，可按下面内容方法递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，接着在其尾部加上xm(=yn)即可得X和Y的壹个最长公共子序列。当xm≠yn时，必须解两个子难题，即找出Xm-1和Y的壹个最长公共子序列及X和Yn-1的壹个最长公共子序列。这两个公共子序列中较长者即为X和Y的壹个最长公共子序列。

由此递归结构容易看到最长公共子序列难题具有子难题重叠性质。在计算X和Y的最长公共子序列时，也许要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子难题都包含壹个公共子难题，即计算Xm-1和Yn-1的最长公共子序列。

大家来建立子难题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1, x2,…, xi>，Yj=<y1, y2,…, yj>。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下：

c)计算最优值

由于在所思考的子难题空间中，总共只有θ(m*n)个不同的子难题，用动态规划算法自底给上地计算最优值能进步算法的效率。

计算最长公共子序列长度的动态规划算法L反恐精英_LENGTH(X,Y)以序列X=<x1, x2,…, xm>和Y=<y1, y2,…, yn>作为输入。输出两个数组c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存储Xi和Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪壹个子难题的解达到的，这在构造最长公共子序列时要用到。X和Y的最长公共子序列的长度记录于c[m,n]中。

程序如下：

#include<stdio.h>

#include<string.h>

int lcs_length(char x[], char y[]);

int main()

{

char x[100],y[100];

int len;

while(1)

{

scanf("%s%s",x,y);

if(x[0]=='0')//约定第壹个字符串以‘0’开始表示结束

break;

len=lcs_length(x,y);

printf("%d\n",len);

}

}

int lcs_length(char x[], char y[])

{

int m,n,i,j,l[100][100];

m=strlen(x);

n=strlen(y);

for(i=0;i<m+1;i++)

l[i][0]=0;

for(j=0;j<n+1;j++)

l[0][j]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if(x[i-1]==y[j-1])//i,j从1开始，但字符串是从0开始

l[i][j]=l[i-1][j-1]+1;

else if(l[i][j-1]>l[i-1][j])

l[i][j]=l[i][j-1];

else

l[i][j]=l[i-1][j];

return l[m][n];

}

由于每个数组单元的计算耗费Ο(1)时刻，算法lcs_length耗时Ο(mn)。

思索：空间能节约吗？

2．计算矩阵连乘积

在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A一个p×q的矩阵，B一个q×r的矩阵，则其乘积C=AB一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：

现在的难题是，给定n个矩阵{A1,A2,…,An}。其中Ai和Ai+1是可乘的，i=1,2,…,n-1。标准计算出这n个矩阵的连乘积A1A2…An。

递归公式：

程序如下：

#include<stdio.h>

int main()

{

int p[101],i,j,k,r,t,n;

int m[101][101];//为了跟讲解时保持一致数组从1开始

int s[101][101];//记录从第i到第j个矩阵连乘的断开位置

scanf("%d",&n);

for(i=0;i<=n;i++)

scanf("%d",&p[i]);//读入p[i]的值(注意：p[0]到p[n]共n+1项)

for(i=1;i<=n;i++)//初始化m[i][i]=0

m[i][i]=0;

for(r=1;r<n;r++)//r为i、j相差的值

for(i=1;i<n;i++)//i为行

{

j=i+r;//j为列

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//给m[i][j]赋初值

s[i][j]=i;

for(k=i+1;k<j;k++)

{

t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(t<m[i][j])

{

m[i][j]=t;//m[i][j]取最小值

s[i][j]=k;

}

}

}

printf("%d",m[1][n]);

}

3．凸多边形的最优三角剖分

多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。壹个简单多边形将平面分为3个部分：被包围在多边形内的全部点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当壹个简单多边形及其内部构成壹个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上全部的点均在该凸多边形的内部或边界上。

通常，用多边形顶点的逆时针序列来表示壹个凸多边形，即P=<v0,v1,…,vn-1>表示具有n条边v0v1，v1v2，…,vn-1vn的壹个凸多边形，约定v0=vn。

若vi和vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形<vi,vi+1,…,vj>和<vj,vj+1,…,vi>。多边形的三角剖分一个将多边形分割成互不重迭的三角形的弦的集中T。如图一个凸多边形的两个不同的三角剖分。

凸多边形最优三角剖分的难题是：给定壹个凸多边形P=<v0,v1,…,vn-1>以及定义在由多边形的边和弦组成的三角形上的权函数ω。标准确定该凸多边形的壹个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。

可以定义三角形上各种各样的权函数W。例如：定义ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。(注意：化解此难题的算法必须适用于任意的权函数)

4．防卫导弹

一种新型的防卫导弹可截击多个攻击导弹。它可以给前飞行，也可以用很快的速度给下飞行，可以毫无损伤地截击进攻导弹，但不可以给后或给上飞行。但有壹个缺点，虽然它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时刻固定，飞行速度相同），该防卫导弹所能获取的信息包括各进攻导弹的高度，以及它们发射次序。现标准编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，壹个导弹能被截击应满足下列两个条件其中一个：

a)它是该次测试中第壹个被防卫导弹截击的导弹；

b)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。

输入数据：第一行一个整数n，以后的n各有壹个整数表示导弹的高度。

输出数据：截击导弹的最大数目。

解析：定义l[i]为选择截击第i个导弹，从这个导弹开始最多能截击的导弹数目。

由于选择了第i枚导弹，因此下壹个要截击的导弹j的高度要小于等于它的高度，因此l[i]应该等于从i＋1到n的每壹个j，满足h[j]<=h[i]的j中l[j]的最大值。

程序如下：

#include<stdio.h>

int main()

{

int i,j,n,max,h[100],l[100];

scanf("%d",&n);

for(i=0;i<n;i++)

scanf("%d",&h[i]);

l[n-1]=1;

for(i=n-2;i>=0;i--)

{

max=0;

for(j=i+1;j<n;j++)

if(h[i]>h[j]&&max<l[j])

max=l[j];

l[i]=max+1;

}

printf("%d",l[0]);

}

5．石子合并

在壹个圆形操场的四周摆放着n堆石子(n<= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，由文件读入堆栈数n及每堆栈的石子数(<=20)。

选择一种合并石子的方法,使得做n－1次合并,得分的总和最小；

输入数据：

第一行为石子堆数n；

第二行为每堆的石子数,每两个数之间用壹个空格分隔。

输出数据：

从第一至第n行为得分最小的合并方法。第n+1行是空行.从第n+2行到第2n+1行是得分最大合并方法。每种合并方法用n行表示，其中第i行(1<=i<=n)表示第i次合并前各堆的石子数(依顺时针次序输出，哪一堆先输出均可)。标准将待合并的两堆石子数以相应的负数表示。

Sample Input

4

4 5 9 4

Sample Output

－4 5 9－4

－8－5 9

－13－9

22 4－5－9 4

4－14－4

－4－18

22

6．最小代价子母树

设有一排数，共n个，例如：22 14 7 13 26 15 11。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。

输入、输出数据格式和“石子合并”相同。

Sample Input

4

12 5 16 4

Sample Output

－12－5 16 4

17－16－4

－17－20

37

7．商店购物

某商店中每种商品都有壹个价格。一朵花的价格是2 ICU(ICU是信息学竞赛的货币的单位）；壹个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了独特优惠价。独特优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6而是5 ICU；2个花瓶加1朵花是10 ICU不是12 ICU。

编壹个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，而且某顾客购买物品为：3朵花和2个花瓶。那么顾客应付款为14 ICU由于：

1朵花加2个花瓶优惠价：10 ICU

2朵花正常价：4 ICU

输入数据：第壹个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。两个文件中都只用整数。

第壹个文件INPUT．TXT的格式为:第一行一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C代表商品的编码（每种商品有壹个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。

第二个文件OFFER．TXT的格式为:第一行一个数字S（0≤S≤9 9），表示共有S种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是多少数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后壹个数字P（1≤ P≤9999）代表此商品组合的优惠价。优惠价要低于该组合中商品正常价之总和。

输出数据：在输出文件OUTPUT．TXT中写壹个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。

8．旅游预算

壹个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下制度：

若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在壹个加油站加油时，司机要花费2元买物品吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。

输入数据：从当前目录下的文这篇文章小编将件“route.dat”读入数据。按下面内容格式输入若干旅行路线的情况：

第一行为起点到终点的距离（实数）

第二行为三个实数，后跟壹个整数，每两个数据间用壹个空格隔开。其中第壹个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用壹个空格分隔，其中第壹个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们和起点的距离升序排列。全部的输入都有一定有解。

输出数据：答案输出到当前目录下的文这篇文章小编将件“route.out”中。该文件包括两行。第一行为壹个实数和壹个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用壹个空格分隔，除了这些之后没有多余的空格。

Sample Input

516.3 38.09 1

15.7 22.1 20.87 3 2

125.4 1.259

297.9 1.129

345.2 0.999

Sample Output

38.09 1

2

9．皇宫看守

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论怎样也没法在每个宫殿都安置留守侍卫。

请你编程计算帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入数据：输入数据由文件名为intput.txt的文这篇文章小编将件提供。输入文件中数据表示一棵树，描述如下：

第1行 n，表示树中结点的数目。

第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i<=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，...，rm。

对于壹个n（0< n<= 1500）个结点的树，结点标号在1到n之间，且标号不重复。

输出数据：输出到output.txt文件中。输出文件仅包含壹个数，为所求的最少的经费。

如右图的输入数据示例：

Sample Input

6

1 30 3 2 3 4

2 16 2 5 6

3 5 0

4 4 0

5 11 0

6 5 0

Sample Output

25

10．游戏室难题

有壹个游戏室里有多个游戏室，而且这每个游戏室里还有多个游戏室，每个游戏室里面还有游戏室，依此类推。进入每个游戏室都可得到一定的高兴，每个游戏室的门票价格都大于等于0，都有壹个高兴值，而且只有进入了壹个游戏室，才可以进入它内部的游戏室，小明现在有n元钱，问最大能得到几许的高兴。

11．*基因难题

已知两个基因序列如s：A圣安地列斯GT；t：ATTAG。现要你给序列中增加一些空格后，首先使得两个序列的长度相等，其次两个串对应符号匹配得到的值最大。基因只有四种分别用A、G、C、T表示，匹配中不允许两个空格相对应，任意两符号的匹配值由下表给出：

A G C T〕

A 5-2-1-2-4

G-2 5-4-3-2

C-1-4 5-5-1

T-2-3-5 5-2

〕-4-2-1-2

提示：定义难题l[i][j]为取第壹个序列的前i项，和第二个序列的前j项，这两个序列加空格匹配的最大值。它的最优值和三个子难题有关，l[i-1][j-1]、l[i][j-1]、l[i-1][j]。

建立递归公式如下：

其中m[0][t[j]表示表中空格和t[j]匹配的对应值。

思索：本难题的初始化。

12．*田忌赛马

田忌和齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王和田忌的每匹马的速度，而且齐王肯定是按马的速度从快到慢出场，现要你写壹个程序帮助田忌计算他最好的结局是赢几许两黄金（输用负数表示）。

解析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本难题应用的算法是动态规划和贪心算法相结合化解的。从两人的最弱的马入手：

若田忌的马快，就让这两匹马比赛；

若田忌的马慢，干脆就让他对付齐王更快的马；

若两匹马的速度相等，这时有两种选择方法，或者它俩比赛，或者对付齐王更快的马。

定义子难题：l(i，j)为齐王的从第i匹马开始的j匹马和田忌的更快的j匹马比赛，田忌所获取的最大收益。

则：

程序具体实现时，为了适合c数据从0开始，稍加变动，定义子难题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马和田忌的更快的j+1匹马比赛，田忌所获取的最大收益。初始化时：l[i][0]表示齐王的第i匹马和田忌更快的马比赛的结局。

程序如下：

#include<stdio.h>

void readdata();

void init();

int n,a[100],b[100],l[100][100];

int main()

{

int i,j;

readdata();

init();

for(i=n-2;i>=0;i--)

for(j=1;j<n-i;j++)

if(a[i+j]<b[j])

l[i][j]=l[i][j-1]+1;

else if(a[i+j]>b[j])

l[i][j]=l[i+1][j-1]-1;

else if(l[i+1][j-1]-1>l[i][j-1])

l[i][j]=l[i+1][j-1]-1;

else

l[i][j]=l[i][j-1];

printf("%d",l[0][n-1]);

}

void readdata()

{

int i;

scanf("%d",&n);

for(i=0;i<n;i++)

scanf("%d",&a[i]);

for(i=0;i<n;i++)

scanf("%d",&b[i]);

}

void init()

{

int i;

// qsort(a,n);//略

for(i=0;i<n;i++)

{

if(a[i]<b[0])

l[i][0]=1;

else if(a[i]==b[0])

l[i][0]=0;

else

l[i][0]=-1;

}

}